package LC;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.com/problems/unique-binary-search-trees-ii/description/
 * Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
 * For example,
 * Given n = 3, your program should return all 5 unique BST's shown below.
 */
public class LC_095_UniqueBinarySearchTreesII_BinaryTree {
    public static void main(String[] args) {
        System.out.println(Solution.generateTrees(4));
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return val + "[ " + left + " " + right + " ]";
        }
    }

    static class Solution {
        static List<TreeNode> generateTrees(int n) {
            if (n <= 0) return new ArrayList<>();
            return generateSubTree(1, n);
        }

        static ArrayList<TreeNode> generateSubTree(int start, int end) {
            ArrayList<TreeNode> result = new ArrayList<>();
            if (start > end) {
                result.add(null);
                return result;
            }
            for (int rootVal = start; rootVal <= end; rootVal++)
                for (TreeNode leftSubTreeRoot : generateSubTree(start, rootVal - 1))
                    for (TreeNode rightSubTreeRoot : generateSubTree(rootVal + 1, end)) {
                        TreeNode root = new TreeNode(rootVal);
                        root.left = leftSubTreeRoot;
                        root.right = rightSubTreeRoot;
                        result.add(root);
                    }
            return result;
        }
    }
}
